#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end

from math import log, ceil


class Solution:
    def intervalSum(self, A, queries):
        # return self.interval_sum_regular(A, queries)
        return self.interval_sum_seg_tree(A, queries)

    # =================== regular method =====================
    def interval_sum_regular(self, A, queries):
        l = len(A)
        pre_sum = [0] * (l + 1)     # 多一位表示0之前的和是0
        ret = []

        for i in range(l):
            pre_sum[i+1] = pre_sum[i] + A[i]

        print(pre_sum)

        for q in queries:
            ret.append( pre_sum[q.end+1] - pre_sum[q.start])

        return ret

    # =================== segment tree  =====================
    def interval_sum_seg_tree(self, A, queries):
        self.A = A
        self.len = len(A)
        self.build_seg_tree()

        ret = []

        # print(type(queries))
        for one_query in queries:
            ret.append( self.query(one_query.start, one_query.end) )

        return ret

    def query(self, qleft, qright):
        # [qleft, qright)
        return self._query_rec(qleft, qright+1, seg_left=0, seg_right=self.len, seg_pos=0)

    def _query_rec(self, qleft, qright, seg_left, seg_right, seg_pos):
        if seg_left >= qleft and seg_right <= qright:
            return self.seg_tree[seg_pos]

        if qleft >= seg_right or qright <= seg_left:
            return 0

        mid = (seg_left + seg_right + 1) // 2
        left_sum  = self._query_rec(qleft, qright, seg_left, mid, seg_pos*2+1)
        right_sum = self._query_rec(qleft, qright, mid, seg_right, seg_pos*2+2)
        # print(left_min, right_min)
        return left_sum + right_sum

    def build_seg_tree(self):
        # seg_size = 4 * self.len
        base_size = ceil(log(self.len, 2))      # 向最小的 2**n 对齐
        seg_size = 2 * (2 ** base_size) - 1
        self.seg_tree = [None] * seg_size

        self._build_rec(0, 0, self.len)
        print(self.seg_tree)


    def _build_rec(self, seg_pos, start, end):
        # [start, end) open-close interval
        # print(start, end)
        assert end > start
        if start + 1 == end:
            self.seg_tree[seg_pos] = self.A[start]
        else:
            mid = (start + end + 1) // 2
            left_sum  = self._build_rec(seg_pos*2+1, start, mid)
            right_sum = self._build_rec(seg_pos*2+2, mid, end)
            self.seg_tree[seg_pos] = left_sum + right_sum

        return self.seg_tree[seg_pos]


def main():
    print("start main")
    s = Solution()
    ret = s.intervalSum([1,2,7,8,5], [Interval(0, 1)])
    print(ret)

if __name__ == "__main__":
    main()
